<!DOCTYPE html>
<html>
  <head>
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
  <meta content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0" name="viewport">
  <meta name="description" content="tong.li&#39;s blog">
  <meta name="keyword" content="彤哥哥博客，95后技术爱好者,现就职于同程旅行/同程艺龙上海分公司，专注于互联网技术分享的平台。">
  
    <link rel="shortcut icon" href="/css/images/icon.png">
  
  <title>
    
      红黑树深入剖析及Java实现 | 彤哥哥的博客
    
  </title>
  <link href="https://cdn.staticfile.org/font-awesome/4.7.0/css/font-awesome.min.css" rel="stylesheet">
  <link href="https://cdn.staticfile.org/nprogress/0.2.0/nprogress.min.css" rel="stylesheet">
  <link href="https://cdn.staticfile.org/highlight.js/9.12.0/styles/tomorrow-night.min.css" rel="stylesheet">
  
<link rel="stylesheet" href="/css/style.css">

  
  <script src="https://cdn.staticfile.org/jquery/3.2.1/jquery.min.js"></script>
  <script src="https://cdn.staticfile.org/geopattern/1.2.3/js/geopattern.min.js"></script>
  <script src="https://cdn.staticfile.org/nprogress/0.2.0/nprogress.min.js"></script>
  
    
<script src="/js/qrious.js"></script>

  
  
  
  
    <!-- MathJax support START -->
    <script type="text/x-mathjax-config">
      MathJax.Hub.Config({
        tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
        }
      });
    </script>

    <script type="text/x-mathjax-config">
      MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
      });
    </script>
    <script type="text/javascript" src="https://cdn.staticfile.org/mathjax/2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
    <!-- MathJax support END -->
  


  
  
    
<script src="/js/local-search.js"></script>


<meta name="generator" content="Hexo 5.4.2"></head>
<div class="wechat-share">
  <img src="/css/images/logo.png" />
</div>
  <body>
    <header class="header fixed-header">
  <div class="header-container">
    <a class="home-link" href="/">
      <div class="logo"></div>
      <span>彤哥哥的博客</span>
    </a>
    <ul class="right-list">
      
        <li class="list-item">
          
            <a href="/" class="item-link">主页</a>
          
        </li>
      
        <li class="list-item">
          
            <a href="/series/" class="item-link">分类</a>
          
        </li>
      
        <li class="list-item">
          
            <a href="/tags/" class="item-link">标签</a>
          
        </li>
      
        <li class="list-item">
          
            <a href="/archives/" class="item-link">归档</a>
          
        </li>
      
        <li class="list-item">
          
            <a href="/project/" class="item-link">项目</a>
          
        </li>
      
        <li class="list-item">
          
            <a href="/about/" class="item-link">关于</a>
          
        </li>
      
      
        <li class="menu-item menu-item-search right-list">
    <a role="button" class="popup-trigger">
        <i class="fa fa-search fa-fw"></i>
    </a>
</li>
      
    </ul>
    <div class="menu">
      <span class="icon-bar"></span>
      <span class="icon-bar"></span>
      <span class="icon-bar"></span>
    </div>
    <div class="menu-mask">
      <ul class="menu-list">
        
          <li class="menu-item">
            
              <a href="/" class="menu-link">主页</a>
            
          </li>
        
          <li class="menu-item">
            
              <a href="/series/" class="menu-link">分类</a>
            
          </li>
        
          <li class="menu-item">
            
              <a href="/tags/" class="menu-link">标签</a>
            
          </li>
        
          <li class="menu-item">
            
              <a href="/archives/" class="menu-link">归档</a>
            
          </li>
        
          <li class="menu-item">
            
              <a href="/project/" class="menu-link">项目</a>
            
          </li>
        
          <li class="menu-item">
            
              <a href="/about/" class="menu-link">关于</a>
            
          </li>
        
      </ul>
    </div>
    
      <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
            <span class="search-icon">
                <i class="fa fa-search"></i>
            </span>
            <div class="search-input-container">
                <input autocomplete="off" autocapitalize="off"
                    placeholder="Please enter your keyword(s) to search." spellcheck="false"
                    type="search" class="search-input">
            </div>
            <span class="popup-btn-close">
                <i class="fa fa-times-circle"></i>
            </span>
        </div>
        <div id="search-result">
            <div id="no-result">
                <i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>
            </div>
        </div>
    </div>
</div>
    
  </div>
</header>

    <div id="article-banner">
  <h2>红黑树深入剖析及Java实现</h2>
  <p class="post-date">2019-03-29</p>
  <div class="arrow-down">
    <a href="javascript:;"></a>
  </div>
</div>
<main class="app-body flex-box">
  <!-- Article START -->
  <article class="post-article">
    <section class="markdown-content"><p>谈到数据结构的树，笔者的印象中还是在大学时期的概念，最早的概念源自于哈夫曼树(最优二叉树)，其他的树结构还有二叉查找树、完全二叉树、平衡二叉树(又分为AVL树、RB红黑树、<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/SBT">SBT</a>、<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/%E4%BC%B8%E5%B1%95%E6%A0%91">伸展树</a>、<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/TREAP">TREAP</a>、<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/%E6%9B%BF%E7%BD%AA%E7%BE%8A%E6%A0%91/13859070">替罪羊树</a> ）、平衡多叉树（B - Tree 和B+ Tree)等，今天我们来研究一下平衡二叉树的RB红黑树，因为RB红黑树在JAVA中的实现还是蛮多的。</p>
<p>红黑树是平衡二叉查找树的一种。为了深入理解红黑树，我们先回忆一下大学数据结构中的二叉查找树。</p>
<h2 id="二叉查找树"><a href="#二叉查找树" class="headerlink" title="二叉查找树"></a>二叉查找树</h2><h3 id="基本概念"><a href="#基本概念" class="headerlink" title="基本概念"></a>基本概念</h3><p>百度百科定义如下：</p>
<blockquote>
<p>二叉排序树（Binary Sort Tree），又称<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%9F%A5%E6%89%BE%E6%A0%91/7077965">二叉查找树</a>（Binary Search Tree），亦称<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/7077855">二叉搜索树</a>。</p>
</blockquote>
<blockquote>
<p>二叉排序树或者是一棵空树，或者是具有下列性质的<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%A0%91">二叉树</a>：</p>
<p>（1）若左子树不空，则左子树上所有结点的值均小于它的<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/%E6%A0%B9%E7%BB%93">根结</a>点的值；</p>
<p>（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；</p>
<p>（3）左、右子树也分别为二叉排序树；</p>
</blockquote>
<p>二叉查找树（Binary Search Tree，简称BST）是一棵二叉树，它的左子节点的值比父节点的值要小，右节点的值要比父节点的值大。它的高度决定了它的查找效率。</p>
<p>在理想的情况下，二叉查找树增删查改的时间复杂度为O(logN)（其中N为节点数），最坏的情况下为O(N)。当它的高度为logN+1时，我们就说二叉查找树是平衡的。</p>
<h3 id="基本操作"><a href="#基本操作" class="headerlink" title="基本操作"></a>基本操作</h3><h4 id="查找"><a href="#查找" class="headerlink" title="查找"></a>查找</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 定义一个搜索的Key</span></span><br><span class="line"><span class="type">T</span>  <span class="variable">key</span> <span class="operator">=</span> a search key</span><br><span class="line"><span class="comment">// 树的节点，当前节点指的是树的根节点</span></span><br><span class="line"><span class="type">Node</span> <span class="variable">root</span> <span class="operator">=</span> point to the root of a BST</span><br><span class="line"><span class="comment">//循环查找树</span></span><br><span class="line"><span class="keyword">while</span>(<span class="literal">true</span>)&#123;</span><br><span class="line">    <span class="comment">// 根节点为空，直接结束，无法继续查询</span></span><br><span class="line">    <span class="keyword">if</span>(root==<span class="literal">null</span>)&#123;</span><br><span class="line">    	<span class="keyword">break</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 如果查找到，直接返回当前的节点</span></span><br><span class="line">    <span class="keyword">if</span>(root.value.equals(key))&#123;</span><br><span class="line">    	<span class="keyword">return</span> root;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 没有查到则做比较继续查询，如果当前要查找的key与当前节点value做比较，若key小于当前节点的value在左子树查找</span></span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">if</span>(key.compareTo(root.value)&lt;<span class="number">0</span>)&#123;</span><br><span class="line">    	root = root.left;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 若key大于当前节点的value在右子树查找</span></span><br><span class="line">    <span class="keyword">else</span>&#123;</span><br><span class="line">      <span class="comment">// 将右字数指向的root节点，继续查找</span></span><br><span class="line">    	root = root.right;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 没有查找则返回null</span></span><br><span class="line"><span class="keyword">return</span> <span class="literal">null</span>;</span><br></pre></td></tr></table></figure>

<p>从程序中可以看出，当BST查找的时候，先与当前节点进行比较：</p>
<ul>
<li>如果相等的话就返回当前节点；</li>
<li>如果少于当前节点则继续查找当前节点的左节点；</li>
<li>如果大于当前节点则继续查找当前节点的右节点</li>
</ul>
<p>直到当前节点指针为空或者查找到对应的节点，程序查找结束。</p>
<h4 id="插入"><a href="#插入" class="headerlink" title="插入"></a>插入</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 新节点</span></span><br><span class="line"><span class="type">Node</span> <span class="variable">node</span> <span class="operator">=</span> create a <span class="keyword">new</span> <span class="title class_">node</span> with specify value</span><br><span class="line"><span class="comment">// 树的节点，默认当前节点指的是树的根节点</span></span><br><span class="line"><span class="type">Node</span> <span class="variable">root</span> <span class="operator">=</span> point the root node of a BST</span><br><span class="line"><span class="comment">// 父节点引用</span></span><br><span class="line"><span class="type">Node</span> <span class="variable">parent</span> <span class="operator">=</span> <span class="literal">null</span>;</span><br><span class="line"></span><br><span class="line"><span class="comment">//find the parent node to append the new node</span></span><br><span class="line"><span class="comment">// 在循环中，找待插入节点的父节点</span></span><br><span class="line"><span class="keyword">while</span>(<span class="literal">true</span>)&#123;</span><br><span class="line">   <span class="comment">// 如果根节点不存在，则直接结束，添加失败。</span></span><br><span class="line">   <span class="keyword">if</span>(root==<span class="literal">null</span>) <span class="keyword">break</span>;</span><br><span class="line">   <span class="comment">// 将父节点指向根节点</span></span><br><span class="line">   parent = root;</span><br><span class="line">   <span class="comment">// 如果新节点的value值小于等于root节点value的，添加到左子树，找左子树的父节点</span></span><br><span class="line">   <span class="keyword">if</span>(node.value.compareTo(root.value)&lt;=<span class="number">0</span>)&#123;</span><br><span class="line">      root = root.left;  </span><br><span class="line">   &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">     <span class="comment">// 否则，添加到右子树，找右子树的父节点</span></span><br><span class="line">      root = root.right;</span><br><span class="line">   &#125; </span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//如果父节点不为null，执行添加操作</span></span><br><span class="line"><span class="keyword">if</span>(parent!=<span class="literal">null</span>)&#123;</span><br><span class="line">   <span class="comment">// 开始添加操作</span></span><br><span class="line">   <span class="keyword">if</span>(node.value.compareTo(parent.value)&lt;=<span class="number">0</span>)&#123;</span><br><span class="line">     <span class="comment">// 添加左子树</span></span><br><span class="line">     <span class="comment">//append to left</span></span><br><span class="line">      parent.left = node;</span><br><span class="line">   &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">      <span class="comment">// append to right</span></span><br><span class="line">      <span class="comment">// 开始添加操作，添加右子树</span></span><br><span class="line">	  parent.right = node;</span><br><span class="line">   &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>插入操作先通过循环查找到待插入的节点的父节点，和查找父节点的逻辑一样，都是比大小，小的往左，大的往右。找到父节点后，对比父节点，小的就插入到父节点的左节点，大就插入到父节点的右节点上。</p>
<h4 id="删除"><a href="#删除" class="headerlink" title="删除"></a>删除</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 待删除节点，可根据查找代码查找出待删除的节点</span></span><br><span class="line"><span class="type">Node</span> <span class="variable">node</span> <span class="operator">=</span> delete a <span class="keyword">new</span> <span class="title class_">node</span> with specify value</span><br><span class="line"></span><br><span class="line"><span class="comment">// 如果节点存在，则进行删除</span></span><br><span class="line"><span class="keyword">if</span> (node != <span class="literal">null</span>) &#123;</span><br><span class="line">   <span class="comment">// 如果节点有左子树，则继续操作</span></span><br><span class="line">   <span class="keyword">if</span> (node.left != <span class="literal">null</span>) &#123;</span><br><span class="line">      <span class="comment">// 找到其左子树的最右边的叶子结点leftR，用该叶子结点leftR来替代待删除的节点node.把leftR的左孩子作为leftR的父亲的右孩子。</span></span><br><span class="line">      <span class="type">Node</span> <span class="variable">leftR</span> <span class="operator">=</span> node.left;</span><br><span class="line">      <span class="comment">// 先前的节点的备份</span></span><br><span class="line">      <span class="type">Node</span> <span class="variable">prev</span> <span class="operator">=</span> node.left;</span><br><span class="line">      <span class="keyword">while</span>(leftR.left != <span class="literal">null</span>) &#123;</span><br><span class="line">         prev = leftR;</span><br><span class="line">         leftR = leftR.right;</span><br><span class="line">      &#125;</span><br><span class="line">      <span class="comment">// 将查找到的leftR.value赋值到node.value</span></span><br><span class="line">      node.value = leftR.value;</span><br><span class="line">      <span class="comment">// 若leftR不是node的左子树,node的左子树不变，leftR的左子树作为leftR的父结点的右孩子结点</span></span><br><span class="line">      <span class="keyword">if</span>(prev != leftR) &#123;</span><br><span class="line">          prev.right = leftR.left;</span><br><span class="line">      &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">         <span class="comment">// 若是leftR的左子树，则node的左子树指向leftR的左子树</span></span><br><span class="line">         node.left=leftR.right;</span><br><span class="line">      &#125;</span><br><span class="line">   &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">       <span class="comment">// 如果节点有左子树，直接用node节点的右孩子取代它</span></span><br><span class="line">       node = node.right;</span><br><span class="line">   &#125;</span><br><span class="line">&#125; </span><br></pre></td></tr></table></figure>

<p>删除操作的步骤如下： </p>
<ul>
<li>查找到要删除的节点。 </li>
<li>如果待删除的节点是叶子节点，即PL(左子树)和PR(右子树)均为空树，由于删去叶子结点不破坏整棵树的结构，则直接删除。 </li>
<li> 如果待删除的节点不是叶子节点，则先找到待删除节点的中序遍历的后继节点，用该后继节点的值替换待删除的节点的值，然后删除后继节点。</li>
</ul>
<h3 id="存在的弊端"><a href="#存在的弊端" class="headerlink" title="存在的弊端"></a>存在的弊端</h3><p>BST存在的主要问题是，数在插入的时候会导致树倾斜，不同的插入顺序会导致树的高度不一样，而树的高度直接的影响了树的查找效率。理想的高度是logN，最坏的情况是所有的节点都在一条斜线上，这样的树的高度为N。</p>
<p>介于以上的弊端，我们有其他新的的树结构选择：Size Balanced Tree(SBT)、AVL树、RB红黑树、<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/Treap">Treap</a>(Tree+Heap)。这些均可以使查找树的高度为O(log(n))。</p>
<h2 id="RB红黑树"><a href="#RB红黑树" class="headerlink" title="RB红黑树"></a>RB红黑树</h2><h3 id="基本概念-1"><a href="#基本概念-1" class="headerlink" title="基本概念"></a>基本概念</h3><blockquote>
<p>红黑树（Red Black Tree） 是一种自平衡二叉查找树，又称对称二叉B树，是在<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/%E8%AE%A1%E7%AE%97%E6%9C%BA">计算机</a>科学中用到的一种<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1450">数据结构</a>，典型的用途是实现<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/%E5%85%B3%E8%81%94%E6%95%B0%E7%BB%84/3317025">关联数组</a>。</p>
<p>它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。</p>
<p>红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。</p>
<p>它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。</p>
</blockquote>
<p>基于BST存在的问题，一种新的树——平衡二叉查找树(Balanced BST)产生了。平衡树在插入和删除的时候，会通过旋转操作将高度保持在logN。其中两款具有代表性的平衡树分别为AVL树和红黑树。AVL树由于实现比较复杂，而且插入和删除性能差，在实际环境下的应用不如红黑树。</p>
<p>红黑树（Red-Black Tree，以下简称RBTree）的实际应用非常广泛，比如Linux内核中的完全公平调度器、高精度计时器、ext3文件系统等等，各种语言的函数库如Java的TreeMap和TreeSet，C++ STL的map、multimap、multiset等。</p>
<p>RBTree也是函数式语言中最常用的持久数据结构之一，在计算几何中也有重要作用。值得一提的是，Java 8中HashMap的实现也因为用RBTree取代链表，性能有所提升。</p>
<h3 id="基本定义"><a href="#基本定义" class="headerlink" title="基本定义"></a>基本定义</h3><p>RBTree的定义如下: </p>
<ul>
<li>任何一个节点都有颜色，黑色或者红色；</li>
<li>根节点是黑色的；</li>
<li>父子节点之间不能出现两个连续的红节点 ；</li>
<li>任何一个节点向下遍历到其子孙的叶子节点，所经过的黑节点个数必须相等 ；</li>
<li>空节点被认为是黑色的。</li>
</ul>
<p>数据结构表示如下：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">lass  Node&lt;T&gt;&#123;</span><br><span class="line">   <span class="keyword">public</span>  T value;</span><br><span class="line">   <span class="keyword">public</span>   Node&lt;T&gt; parent;</span><br><span class="line">   <span class="keyword">public</span>   <span class="type">boolean</span> isRed;</span><br><span class="line">   <span class="keyword">public</span>   Node&lt;T&gt; left;</span><br><span class="line">   <span class="keyword">public</span>   Node&lt;T&gt; right;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>RBTree在理论上还是一棵BST树，但是它在对BST的插入和删除操作时会维持树的平衡，即保证树的高度在[logN,logN+1]（理论上，极端的情况下可以出现RBTree的高度达到2*logN，但实际上很难遇到）。这样RBTree的查找时间复杂度始终保持在O(logN)从而接近于理想的BST。RBTree的删除和插入操作的时间复杂度也是O(logN)。RBTree的查找操作就是BST的查找操作。</p>
<h3 id="基本操作-1"><a href="#基本操作-1" class="headerlink" title="基本操作"></a>基本操作</h3><h4 id="旋转操作"><a href="#旋转操作" class="headerlink" title="旋转操作"></a>旋转操作</h4><p>旋转操作(Rotate)的目的是使节点颜色符合定义，让RBTree的高度达到平衡。 Rotate分为left-rotate（左旋）和right-rotate（右旋），区分左旋和右旋的方法是：待旋转的节点从左边上升到父节点就是右旋，待旋转的节点从右边上升到父节点就是左旋。</p>
<h4 id="查找操作"><a href="#查找操作" class="headerlink" title="查找操作"></a>查找操作</h4><p>RBTree的查找操作和BST的查找操作是一样的。请参考BST的查找操作代码。</p>
<h4 id="插入操作"><a href="#插入操作" class="headerlink" title="插入操作"></a>插入操作</h4><p>RBTree的插入与BST的插入方式是一致的，只不过是在插入过后，可能会导致树的不平衡，这时就需要对树进行旋转操作和颜色修复（在这里简称插入修复），使得它符合RBTree的定义。</p>
<p>新插入的节点是红色的，插入修复操作如果遇到父节点的颜色为黑则修复操作结束。也就是说，只有在父节点为红色节点的时候是需要插入修复操作的。</p>
<p>插入修复操作分为以下的三种情况，而且新插入的节点的父节点都是红色的：</p>
<ol>
<li>叔叔节点也为红色。</li>
<li>叔叔节点为空，且祖父节点、父节点和新节点处于一条斜线上。</li>
<li>叔叔节点为空，且祖父节点、父节点和新节点不处于一条斜线上。</li>
</ol>
<ul>
<li><p>插入操作示例1</p>
<p>示例1的操作是将父节点和叔叔节点与祖父节点的颜色互换，这样就符合了RBTRee的定义。即维持了高度的平衡，修复后颜色也符合RBTree定义的第三条和第四条。下图中，操作完成后A节点变成了新的节点。如果A节点的父节点不是黑色的话，则继续做修复操作。</p>
</li>
</ul>
<p><img src="https://ltyeamin.github.io/imgs/2020/07/20200731172357.png" alt="插入修复示例1"></p>
<ul>
<li>插入操作示例2</li>
</ul>
<p>示例2的操作是将B节点进行右旋操作，并且和父节点A互换颜色。通过该修复操作RBTRee的高度和颜色都符合红黑树的定义。如果B和C节点都是右节点的话，只要将操作变成左旋就可以了。</p>
<p><img src="https://ltyeamin.github.io/imgs/2020/07/20200731172401.png" alt="插入修复示例2"></p>
<ul>
<li>插入操作示例3</li>
</ul>
<p>示例 3的操作是将C节点进行左旋，这样就从示例 3转换成示例 2了，然后针对示例 2进行操作处理就行了。示例 2操作做了一个右旋操作和颜色互换来达到目的。如果树的结构是下图的镜像结构，则只需要将对应的左旋变成右旋，右旋变成左旋即可。</p>
<p><img src="https://ltyeamin.github.io/imgs/2020/07/20200731172406.png" alt="插入修复3"></p>
<p>插入操作的总结:</p>
<p>插入后的修复操作是一个向root节点回溯的操作，一旦牵涉的节点都符合了红黑树的定义，修复操作结束。之所以会向上回溯是由于示例 1操作会将父节点，叔叔节点和祖父节点进行换颜色，有可能会导致祖父节点不平衡(红黑树定义3)。这个时候需要对祖父节点为起点进行调节（向上回溯）。</p>
<p>祖父节点调节后如果还是遇到它的祖父颜色问题，操作就会继续向上回溯，直到root节点为止，根据定义root节点永远是黑色的。在向上的追溯的过程中，针对插入的3中情况进行调节。直到符合红黑树的定义为止。直到牵涉的节点都符合了红黑树的定义，修复操作结束。</p>
<p>如果上面的3中情况如果对应的操作是在右子树上，做对应的镜像操作就是了。</p>
<h4 id="删除操作"><a href="#删除操作" class="headerlink" title="删除操作"></a>删除操作</h4><p>删除操作首先需要做的也是BST的删除操作，删除操作会删除对应的节点，如果是叶子节点就直接删除，如果是非叶子节点，会用对应的中序遍历的后继节点来顶替要删除节点的位置。删除后就需要做删除修复操作，使的树符合红黑树的定义，符合定义的红黑树高度是平衡的。</p>
<p>删除修复操作在遇到被删除的节点是红色节点或者到达root节点时，修复操作完毕。</p>
<p>删除修复操作是针对删除黑色节点才有的，当黑色节点被删除后会让整个树不符合RBTree的定义的第四条。需要做的处理是从兄弟节点上借调黑色的节点过来，如果兄弟节点没有黑节点可以借调的话，就只能往上追溯，将每一级的黑节点数减去一个，使得整棵树符合红黑树的定义。</p>
<p>删除操作的总体思想是从兄弟节点借调黑色节点使树保持局部的平衡，如果局部的平衡达到了，就看整体的树是否是平衡的，如果不平衡就接着向上追溯调整。</p>
<p>删除修复操作分为四种情况(删除黑节点后)：</p>
<ol>
<li>待删除的节点的兄弟节点是红色的节点。</li>
<li>待删除的节点的兄弟节点是黑色的节点，且兄弟节点的子节点都是黑色的。</li>
<li>待调整的节点的兄弟节点是黑色的节点，且兄弟节点的左子节点是红色的，右节点是黑色的(兄弟节点在右边)，     如果兄弟节点在左边的话，就是兄弟节点的右子节点是红色的，左节点是黑色的。 </li>
<li>待调整的节点的兄弟节点是黑色的节点，且右子节点是是红色的(兄弟节点在右边)，如果兄弟节点在左边，则就是对应的就是左节点是红色的。</li>
</ol>
<ul>
<li>删除操作示例1</li>
</ul>
<p>由于兄弟节点是红色节点的时候，无法借调黑节点，所以需要将兄弟节点提升到父节点，由于兄弟节点是红色的，根据RBTree的定义，兄弟节点的子节点是黑色的，就可以从它的子节点借调了。</p>
<p>示例1这样转换之后就会变成后面的示例2，示例3，或者示例4进行处理了。上升操作需要对C做一个左旋操作，如果是镜像结构的树只需要做对应的右旋操作即可。</p>
<p>之所以要做示例1操作是因为兄弟节点是红色的，无法借到一个黑节点来填补删除的黑节点。</p>
<p><img src="https://ltyeamin.github.io/imgs/2020/07/20200731172410.png" alt="删除情况1"></p>
<ul>
<li>删除操作示例2</li>
</ul>
<p>示例2的删除操作是由于兄弟节点可以消除一个黑色节点，因为兄弟节点和兄弟节点的子节点都是黑色的，所以可以将兄弟节点变红，这样就可以保证树的局部的颜色符合定义了。这个时候需要将父节点A变成新的节点，继续向上调整，直到整颗树的颜色符合RBTree的定义为止。</p>
<p>示例2这种情况下之所以要将兄弟节点变红，是因为如果把兄弟节点借调过来，会导致兄弟的结构不符合RBTree的定义，这样的情况下只能是将兄弟节点也变成红色来达到颜色的平衡。当将兄弟节点也变红之后，达到了局部的平衡了，但是对于祖父节点来说是不符合定义4的。这样就需要回溯到父节点，接着进行修复操作。</p>
<p><img src="https://ltyeamin.github.io/imgs/2020/07/20200731172414.png" alt="删除情况2"></p>
<ul>
<li>删除操作示例3</li>
</ul>
<p>示例3的删除操作是一个中间步骤，它的目的是将左边的红色节点借调过来，这样就可以转换成示例4状态了，在示例4状态下可以将D，E节点都阶段过来，通过将两个节点变成黑色来保证红黑树的整体平衡。</p>
<p>之所以说case-3是一个中间状态，是因为根据红黑树的定义来说，下图并不是平衡的，他是通过示例2操作完后向上回溯出现的状态。之所以会出现示例3和后面的示例4的情况，是因为可以通过借用侄子节点的红色，变成黑色来符合红黑树定义4.</p>
<p><img src="https://ltyeamin.github.io/imgs/2020/07/20200731172420.png" alt="删除情况3"></p>
<ul>
<li>删除操作示例4</li>
</ul>
<p>示例4的操作是真正的节点借调操作，通过将兄弟节点以及兄弟节点的右节点借调过来，并将兄弟节点的右子节点变成红色来达到借调两个黑节点的目的，这样的话，整棵树还是符合RBTree的定义的。</p>
<p>示例4这种情况的发生只有在待删除的节点的兄弟节点为黑，且子节点不全部为黑，才有可能借调到两个节点来做黑节点使用，从而保持整棵树都符合红黑树的定义。</p>
<p><img src="https://ltyeamin.github.io/imgs/2020/07/20200731172424.png" alt="删除情况4"></p>
<p>删除操作的总结:</p>
<p>红黑树的删除操作是最复杂的操作，复杂的地方就在于当删除了黑色节点的时候，如何从兄弟节点去借调节点，以保证树的颜色符合定义。由于红色的兄弟节点是没法借调出黑节点的，这样只能通过选择操作让他上升到父节点，而由于它是红节点，所以它的子节点就是黑的，可以借调。</p>
<p>对于兄弟节点是黑色节点的可以分成3种情况来处理，当所以的兄弟节点的子节点都是黑色节点时，可以直接将兄弟节点变红，这样局部的红黑树颜色是符合定义的。但是整颗树不一定是符合红黑树定义的，需要往上追溯继续调整。</p>
<p>对于兄弟节点的子节点为左红右黑或者 (全部为红，右红左黑)这两种情况，可以先将前面的情况通过选择转换为后一种情况，在后一种情况下，因为兄弟节点为黑，兄弟节点的右节点为红，可以借调出两个节点出来做黑节点，这样就可以保证删除了黑节点，整棵树还是符合红黑树的定义的，因为黑色节点的个数没有改变。</p>
<p>红黑树的删除操作是遇到删除的节点为红色，或者追溯调整到了root节点，这时删除的修复操作完毕。</p>
<h2 id="RB红黑树的Java实现"><a href="#RB红黑树的Java实现" class="headerlink" title="RB红黑树的Java实现"></a>RB红黑树的Java实现</h2><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br><span class="line">189</span><br><span class="line">190</span><br><span class="line">191</span><br><span class="line">192</span><br><span class="line">193</span><br><span class="line">194</span><br><span class="line">195</span><br><span class="line">196</span><br><span class="line">197</span><br><span class="line">198</span><br><span class="line">199</span><br><span class="line">200</span><br><span class="line">201</span><br><span class="line">202</span><br><span class="line">203</span><br><span class="line">204</span><br><span class="line">205</span><br><span class="line">206</span><br><span class="line">207</span><br><span class="line">208</span><br><span class="line">209</span><br><span class="line">210</span><br><span class="line">211</span><br><span class="line">212</span><br><span class="line">213</span><br><span class="line">214</span><br><span class="line">215</span><br><span class="line">216</span><br><span class="line">217</span><br><span class="line">218</span><br><span class="line">219</span><br><span class="line">220</span><br><span class="line">221</span><br><span class="line">222</span><br><span class="line">223</span><br><span class="line">224</span><br><span class="line">225</span><br><span class="line">226</span><br><span class="line">227</span><br><span class="line">228</span><br><span class="line">229</span><br><span class="line">230</span><br><span class="line">231</span><br><span class="line">232</span><br><span class="line">233</span><br><span class="line">234</span><br><span class="line">235</span><br><span class="line">236</span><br><span class="line">237</span><br><span class="line">238</span><br><span class="line">239</span><br><span class="line">240</span><br><span class="line">241</span><br><span class="line">242</span><br><span class="line">243</span><br><span class="line">244</span><br><span class="line">245</span><br><span class="line">246</span><br><span class="line">247</span><br><span class="line">248</span><br><span class="line">249</span><br><span class="line">250</span><br><span class="line">251</span><br><span class="line">252</span><br><span class="line">253</span><br><span class="line">254</span><br><span class="line">255</span><br><span class="line">256</span><br><span class="line">257</span><br><span class="line">258</span><br><span class="line">259</span><br><span class="line">260</span><br><span class="line">261</span><br><span class="line">262</span><br><span class="line">263</span><br><span class="line">264</span><br><span class="line">265</span><br><span class="line">266</span><br><span class="line">267</span><br><span class="line">268</span><br><span class="line">269</span><br><span class="line">270</span><br><span class="line">271</span><br><span class="line">272</span><br><span class="line">273</span><br><span class="line">274</span><br><span class="line">275</span><br><span class="line">276</span><br><span class="line">277</span><br><span class="line">278</span><br><span class="line">279</span><br><span class="line">280</span><br><span class="line">281</span><br><span class="line">282</span><br><span class="line">283</span><br><span class="line">284</span><br><span class="line">285</span><br><span class="line">286</span><br><span class="line">287</span><br><span class="line">288</span><br><span class="line">289</span><br><span class="line">290</span><br><span class="line">291</span><br><span class="line">292</span><br><span class="line">293</span><br><span class="line">294</span><br><span class="line">295</span><br><span class="line">296</span><br><span class="line">297</span><br><span class="line">298</span><br><span class="line">299</span><br><span class="line">300</span><br><span class="line">301</span><br><span class="line">302</span><br><span class="line">303</span><br><span class="line">304</span><br><span class="line">305</span><br><span class="line">306</span><br><span class="line">307</span><br><span class="line">308</span><br><span class="line">309</span><br><span class="line">310</span><br><span class="line">311</span><br><span class="line">312</span><br><span class="line">313</span><br><span class="line">314</span><br><span class="line">315</span><br><span class="line">316</span><br><span class="line">317</span><br><span class="line">318</span><br><span class="line">319</span><br><span class="line">320</span><br><span class="line">321</span><br><span class="line">322</span><br><span class="line">323</span><br><span class="line">324</span><br><span class="line">325</span><br><span class="line">326</span><br><span class="line">327</span><br><span class="line">328</span><br><span class="line">329</span><br><span class="line">330</span><br><span class="line">331</span><br><span class="line">332</span><br><span class="line">333</span><br><span class="line">334</span><br><span class="line">335</span><br><span class="line">336</span><br><span class="line">337</span><br><span class="line">338</span><br><span class="line">339</span><br><span class="line">340</span><br><span class="line">341</span><br><span class="line">342</span><br><span class="line">343</span><br><span class="line">344</span><br><span class="line">345</span><br><span class="line">346</span><br><span class="line">347</span><br><span class="line">348</span><br><span class="line">349</span><br><span class="line">350</span><br><span class="line">351</span><br><span class="line">352</span><br><span class="line">353</span><br><span class="line">354</span><br><span class="line">355</span><br><span class="line">356</span><br><span class="line">357</span><br><span class="line">358</span><br><span class="line">359</span><br><span class="line">360</span><br><span class="line">361</span><br><span class="line">362</span><br><span class="line">363</span><br><span class="line">364</span><br><span class="line">365</span><br><span class="line">366</span><br><span class="line">367</span><br><span class="line">368</span><br><span class="line">369</span><br><span class="line">370</span><br><span class="line">371</span><br><span class="line">372</span><br><span class="line">373</span><br><span class="line">374</span><br><span class="line">375</span><br><span class="line">376</span><br><span class="line">377</span><br><span class="line">378</span><br><span class="line">379</span><br><span class="line">380</span><br><span class="line">381</span><br><span class="line">382</span><br><span class="line">383</span><br><span class="line">384</span><br><span class="line">385</span><br><span class="line">386</span><br><span class="line">387</span><br><span class="line">388</span><br><span class="line">389</span><br><span class="line">390</span><br><span class="line">391</span><br><span class="line">392</span><br><span class="line">393</span><br><span class="line">394</span><br><span class="line">395</span><br><span class="line">396</span><br><span class="line">397</span><br><span class="line">398</span><br><span class="line">399</span><br><span class="line">400</span><br><span class="line">401</span><br><span class="line">402</span><br><span class="line">403</span><br><span class="line">404</span><br><span class="line">405</span><br><span class="line">406</span><br><span class="line">407</span><br><span class="line">408</span><br><span class="line">409</span><br><span class="line">410</span><br><span class="line">411</span><br><span class="line">412</span><br><span class="line">413</span><br><span class="line">414</span><br><span class="line">415</span><br><span class="line">416</span><br><span class="line">417</span><br><span class="line">418</span><br><span class="line">419</span><br><span class="line">420</span><br><span class="line">421</span><br><span class="line">422</span><br><span class="line">423</span><br><span class="line">424</span><br><span class="line">425</span><br><span class="line">426</span><br><span class="line">427</span><br><span class="line">428</span><br><span class="line">429</span><br><span class="line">430</span><br><span class="line">431</span><br><span class="line">432</span><br><span class="line">433</span><br><span class="line">434</span><br><span class="line">435</span><br><span class="line">436</span><br><span class="line">437</span><br><span class="line">438</span><br><span class="line">439</span><br><span class="line">440</span><br><span class="line">441</span><br><span class="line">442</span><br><span class="line">443</span><br><span class="line">444</span><br><span class="line">445</span><br><span class="line">446</span><br><span class="line">447</span><br><span class="line">448</span><br><span class="line">449</span><br><span class="line">450</span><br><span class="line">451</span><br><span class="line">452</span><br><span class="line">453</span><br><span class="line">454</span><br><span class="line">455</span><br><span class="line">456</span><br><span class="line">457</span><br><span class="line">458</span><br><span class="line">459</span><br><span class="line">460</span><br><span class="line">461</span><br><span class="line">462</span><br><span class="line">463</span><br><span class="line">464</span><br><span class="line">465</span><br><span class="line">466</span><br><span class="line">467</span><br><span class="line">468</span><br><span class="line">469</span><br><span class="line">470</span><br><span class="line">471</span><br><span class="line">472</span><br><span class="line">473</span><br><span class="line">474</span><br><span class="line">475</span><br><span class="line">476</span><br><span class="line">477</span><br><span class="line">478</span><br><span class="line">479</span><br><span class="line">480</span><br><span class="line">481</span><br><span class="line">482</span><br><span class="line">483</span><br><span class="line">484</span><br><span class="line">485</span><br><span class="line">486</span><br><span class="line">487</span><br><span class="line">488</span><br><span class="line">489</span><br><span class="line">490</span><br><span class="line">491</span><br><span class="line">492</span><br><span class="line">493</span><br><span class="line">494</span><br><span class="line">495</span><br><span class="line">496</span><br><span class="line">497</span><br><span class="line">498</span><br><span class="line">499</span><br><span class="line">500</span><br><span class="line">501</span><br><span class="line">502</span><br><span class="line">503</span><br><span class="line">504</span><br><span class="line">505</span><br><span class="line">506</span><br><span class="line">507</span><br><span class="line">508</span><br><span class="line">509</span><br><span class="line">510</span><br><span class="line">511</span><br><span class="line">512</span><br><span class="line">513</span><br><span class="line">514</span><br><span class="line">515</span><br><span class="line">516</span><br><span class="line">517</span><br><span class="line">518</span><br><span class="line">519</span><br><span class="line">520</span><br><span class="line">521</span><br><span class="line">522</span><br><span class="line">523</span><br><span class="line">524</span><br><span class="line">525</span><br><span class="line">526</span><br><span class="line">527</span><br><span class="line">528</span><br><span class="line">529</span><br><span class="line">530</span><br><span class="line">531</span><br><span class="line">532</span><br><span class="line">533</span><br><span class="line">534</span><br><span class="line">535</span><br><span class="line">536</span><br><span class="line">537</span><br><span class="line">538</span><br><span class="line">539</span><br><span class="line">540</span><br><span class="line">541</span><br><span class="line">542</span><br><span class="line">543</span><br><span class="line">544</span><br><span class="line">545</span><br><span class="line">546</span><br><span class="line">547</span><br><span class="line">548</span><br><span class="line">549</span><br><span class="line">550</span><br><span class="line">551</span><br><span class="line">552</span><br><span class="line">553</span><br><span class="line">554</span><br><span class="line">555</span><br><span class="line">556</span><br><span class="line">557</span><br><span class="line">558</span><br><span class="line">559</span><br><span class="line">560</span><br><span class="line">561</span><br><span class="line">562</span><br><span class="line">563</span><br><span class="line">564</span><br><span class="line">565</span><br><span class="line">566</span><br><span class="line">567</span><br><span class="line">568</span><br><span class="line">569</span><br><span class="line">570</span><br><span class="line">571</span><br><span class="line">572</span><br><span class="line">573</span><br><span class="line">574</span><br><span class="line">575</span><br><span class="line">576</span><br><span class="line">577</span><br><span class="line">578</span><br><span class="line">579</span><br><span class="line">580</span><br><span class="line">581</span><br><span class="line">582</span><br><span class="line">583</span><br><span class="line">584</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">RBTreeNode</span>&lt;T <span class="keyword">extends</span> <span class="title class_">Comparable</span>&lt;T&gt;&gt; &#123;</span><br><span class="line">	<span class="keyword">private</span> T value;<span class="comment">//node value</span></span><br><span class="line">	<span class="keyword">private</span> RBTreeNode&lt;T&gt; left;<span class="comment">//left child pointer</span></span><br><span class="line">	<span class="keyword">private</span> RBTreeNode&lt;T&gt; right;<span class="comment">//right child pointer</span></span><br><span class="line">	<span class="keyword">private</span> RBTreeNode&lt;T&gt; parent;<span class="comment">//parent pointer</span></span><br><span class="line">	<span class="keyword">private</span> <span class="type">boolean</span> red;<span class="comment">//color is red or not red</span></span><br><span class="line">	</span><br><span class="line">	<span class="keyword">public</span> <span class="title function_">RBTreeNode</span><span class="params">()</span>&#123;&#125;</span><br><span class="line">	<span class="keyword">public</span> <span class="title function_">RBTreeNode</span><span class="params">(T value)</span>&#123;<span class="built_in">this</span>.value=value;&#125;</span><br><span class="line">	<span class="keyword">public</span> <span class="title function_">RBTreeNode</span><span class="params">(T value,<span class="type">boolean</span> isRed)</span>&#123;<span class="built_in">this</span>.value=value;<span class="built_in">this</span>.red = isRed;&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">public</span> T <span class="title function_">getValue</span><span class="params">()</span> &#123;</span><br><span class="line">		<span class="keyword">return</span> value;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">void</span> <span class="title function_">setValue</span><span class="params">(T value)</span> &#123;</span><br><span class="line">		<span class="built_in">this</span>.value = value;</span><br><span class="line">	&#125;</span><br><span class="line">	RBTreeNode&lt;T&gt; <span class="title function_">getLeft</span><span class="params">()</span> &#123;</span><br><span class="line">		<span class="keyword">return</span> left;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">void</span> <span class="title function_">setLeft</span><span class="params">(RBTreeNode&lt;T&gt; left)</span> &#123;</span><br><span class="line">		<span class="built_in">this</span>.left = left;</span><br><span class="line">	&#125;</span><br><span class="line">	RBTreeNode&lt;T&gt; <span class="title function_">getRight</span><span class="params">()</span> &#123;</span><br><span class="line">		<span class="keyword">return</span> right;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">void</span> <span class="title function_">setRight</span><span class="params">(RBTreeNode&lt;T&gt; right)</span> &#123;</span><br><span class="line">		<span class="built_in">this</span>.right = right;</span><br><span class="line">	&#125;</span><br><span class="line">	RBTreeNode&lt;T&gt; <span class="title function_">getParent</span><span class="params">()</span> &#123;</span><br><span class="line">		<span class="keyword">return</span> parent;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">void</span> <span class="title function_">setParent</span><span class="params">(RBTreeNode&lt;T&gt; parent)</span> &#123;</span><br><span class="line">		<span class="built_in">this</span>.parent = parent;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="type">boolean</span> <span class="title function_">isRed</span><span class="params">()</span> &#123;</span><br><span class="line">		<span class="keyword">return</span> red;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="type">boolean</span> <span class="title function_">isBlack</span><span class="params">()</span>&#123;</span><br><span class="line">		<span class="keyword">return</span> !red;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">/**</span></span><br><span class="line"><span class="comment">	* is leaf node</span></span><br><span class="line"><span class="comment">	**/</span></span><br><span class="line">	<span class="type">boolean</span> <span class="title function_">isLeaf</span><span class="params">()</span>&#123;</span><br><span class="line">		<span class="keyword">return</span> left==<span class="literal">null</span> &amp;&amp; right==<span class="literal">null</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">void</span> <span class="title function_">setRed</span><span class="params">(<span class="type">boolean</span> red)</span> &#123;</span><br><span class="line">		<span class="built_in">this</span>.red = red;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">void</span> <span class="title function_">makeRed</span><span class="params">()</span>&#123;</span><br><span class="line">		red=<span class="literal">true</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">void</span> <span class="title function_">makeBlack</span><span class="params">()</span>&#123;</span><br><span class="line">		red=<span class="literal">false</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="meta">@Override</span></span><br><span class="line">	<span class="keyword">public</span> String <span class="title function_">toString</span><span class="params">()</span>&#123;</span><br><span class="line">		<span class="keyword">return</span> value.toString();</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">RBTree</span>&lt;T <span class="keyword">extends</span> <span class="title class_">Comparable</span>&lt;T&gt;&gt; &#123;</span><br><span class="line">	<span class="keyword">private</span> <span class="keyword">final</span> RBTreeNode&lt;T&gt; root;</span><br><span class="line">	<span class="comment">//node number</span></span><br><span class="line">	<span class="keyword">private</span> java.util.concurrent.atomic.<span class="type">AtomicLong</span> <span class="variable">size</span> <span class="operator">=</span> </span><br><span class="line">					<span class="keyword">new</span> <span class="title class_">java</span>.util.concurrent.atomic.AtomicLong(<span class="number">0</span>);</span><br><span class="line">	</span><br><span class="line">	<span class="comment">//in overwrite mode,all node&#x27;s value can not  has same	value</span></span><br><span class="line">	<span class="comment">//in non-overwrite mode,node can have same value, suggest don&#x27;t use non-overwrite mode.</span></span><br><span class="line">	<span class="keyword">private</span> <span class="keyword">volatile</span> <span class="type">boolean</span> overrideMode=<span class="literal">true</span>;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">public</span> <span class="title function_">RBTree</span><span class="params">()</span>&#123;</span><br><span class="line">		<span class="built_in">this</span>.root = <span class="keyword">new</span> <span class="title class_">RBTreeNode</span>&lt;T&gt;();</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">public</span> <span class="title function_">RBTree</span><span class="params">(<span class="type">boolean</span> overrideMode)</span>&#123;</span><br><span class="line">		<span class="built_in">this</span>();</span><br><span class="line">		<span class="built_in">this</span>.overrideMode=overrideMode;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">public</span> <span class="type">boolean</span> <span class="title function_">isOverrideMode</span><span class="params">()</span> &#123;</span><br><span class="line">		<span class="keyword">return</span> overrideMode;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">setOverrideMode</span><span class="params">(<span class="type">boolean</span> overrideMode)</span> &#123;</span><br><span class="line">		<span class="built_in">this</span>.overrideMode = overrideMode;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">/**</span></span><br><span class="line"><span class="comment">	 * number of tree number</span></span><br><span class="line"><span class="comment">	 * <span class="doctag">@return</span></span></span><br><span class="line"><span class="comment">	 */</span></span><br><span class="line">	<span class="keyword">public</span> <span class="type">long</span> <span class="title function_">getSize</span><span class="params">()</span> &#123;</span><br><span class="line">		<span class="keyword">return</span> size.get();</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">/**</span></span><br><span class="line"><span class="comment">	 * get the root node</span></span><br><span class="line"><span class="comment">	 * <span class="doctag">@return</span></span></span><br><span class="line"><span class="comment">	 */</span></span><br><span class="line">	<span class="keyword">private</span> RBTreeNode&lt;T&gt; <span class="title function_">getRoot</span><span class="params">()</span>&#123;</span><br><span class="line">		<span class="keyword">return</span> root.getLeft();</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="comment">/**</span></span><br><span class="line"><span class="comment">	 * add value to a new node,if this value exist in this tree,</span></span><br><span class="line"><span class="comment">	 * if value exist,it will return the exist value.otherwise return null</span></span><br><span class="line"><span class="comment">	 * if override mode is true,if value exist in the tree,</span></span><br><span class="line"><span class="comment">	 * it will override the old value in the tree</span></span><br><span class="line"><span class="comment">	 * </span></span><br><span class="line"><span class="comment">	 * <span class="doctag">@param</span> value</span></span><br><span class="line"><span class="comment">	 * <span class="doctag">@return</span></span></span><br><span class="line"><span class="comment">	 */</span></span><br><span class="line">	<span class="keyword">public</span> T <span class="title function_">addNode</span><span class="params">(T value)</span>&#123;</span><br><span class="line">		RBTreeNode&lt;T&gt; t = <span class="keyword">new</span> <span class="title class_">RBTreeNode</span>&lt;T&gt;(value);</span><br><span class="line">		<span class="keyword">return</span> addNode(t);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">/**</span></span><br><span class="line"><span class="comment">	 * find the value by give value(include key,key used for search,</span></span><br><span class="line"><span class="comment">	 * other field is not used,<span class="doctag">@see</span> compare method).if this value not exist return null</span></span><br><span class="line"><span class="comment">	 * <span class="doctag">@param</span> value</span></span><br><span class="line"><span class="comment">	 * <span class="doctag">@return</span></span></span><br><span class="line"><span class="comment">	 */</span></span><br><span class="line">	<span class="keyword">public</span> T <span class="title function_">find</span><span class="params">(T value)</span>&#123;</span><br><span class="line">		RBTreeNode&lt;T&gt; dataRoot = getRoot();</span><br><span class="line">		<span class="keyword">while</span>(dataRoot!=<span class="literal">null</span>)&#123;</span><br><span class="line">			<span class="type">int</span> <span class="variable">cmp</span> <span class="operator">=</span> dataRoot.getValue().compareTo(value);</span><br><span class="line">			<span class="keyword">if</span>(cmp&lt;<span class="number">0</span>)&#123;</span><br><span class="line">				dataRoot = dataRoot.getRight();</span><br><span class="line">			&#125;<span class="keyword">else</span> <span class="keyword">if</span>(cmp&gt;<span class="number">0</span>)&#123;</span><br><span class="line">				dataRoot = dataRoot.getLeft();</span><br><span class="line">			&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">				<span class="keyword">return</span> dataRoot.getValue();</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">/**</span></span><br><span class="line"><span class="comment">	 * remove the node by give value,if this value not exists in tree return null</span></span><br><span class="line"><span class="comment">	 * <span class="doctag">@param</span> value include search key</span></span><br><span class="line"><span class="comment">	 * <span class="doctag">@return</span> the value contain in the removed node</span></span><br><span class="line"><span class="comment">	 */</span></span><br><span class="line">	<span class="keyword">public</span> T <span class="title function_">remove</span><span class="params">(T value)</span>&#123;</span><br><span class="line">		RBTreeNode&lt;T&gt; dataRoot = getRoot();</span><br><span class="line">		RBTreeNode&lt;T&gt; parent = root;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">while</span>(dataRoot!=<span class="literal">null</span>)&#123;</span><br><span class="line">			<span class="type">int</span> <span class="variable">cmp</span> <span class="operator">=</span> dataRoot.getValue().compareTo(value);</span><br><span class="line">			<span class="keyword">if</span>(cmp&lt;<span class="number">0</span>)&#123;</span><br><span class="line">				parent = dataRoot;</span><br><span class="line">				dataRoot = dataRoot.getRight();</span><br><span class="line">			&#125;<span class="keyword">else</span> <span class="keyword">if</span>(cmp&gt;<span class="number">0</span>)&#123;</span><br><span class="line">				parent = dataRoot;</span><br><span class="line">				dataRoot = dataRoot.getLeft();</span><br><span class="line">			&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">				<span class="keyword">if</span>(dataRoot.getRight()!=<span class="literal">null</span>)&#123;</span><br><span class="line">					RBTreeNode&lt;T&gt; min = removeMin(dataRoot.getRight());</span><br><span class="line">					<span class="comment">//x used for fix color balance</span></span><br><span class="line">					RBTreeNode&lt;T&gt; x = min.getRight()==<span class="literal">null</span> ? min.getParent() : min.getRight();</span><br><span class="line">					<span class="type">boolean</span> <span class="variable">isParent</span> <span class="operator">=</span> min.getRight()==<span class="literal">null</span>;</span><br><span class="line">							</span><br><span class="line">					min.setLeft(dataRoot.getLeft());</span><br><span class="line">					setParent(dataRoot.getLeft(),min);</span><br><span class="line">					<span class="keyword">if</span>(parent.getLeft()==dataRoot)&#123;</span><br><span class="line">						parent.setLeft(min);</span><br><span class="line">					&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">						parent.setRight(min);</span><br><span class="line">					&#125;</span><br><span class="line">					setParent(min,parent);</span><br><span class="line">					</span><br><span class="line">					<span class="type">boolean</span> <span class="variable">curMinIsBlack</span> <span class="operator">=</span> min.isBlack();</span><br><span class="line">					<span class="comment">//inherit dataRoot&#x27;s color</span></span><br><span class="line">					min.setRed(dataRoot.isRed());</span><br><span class="line">					</span><br><span class="line">					<span class="keyword">if</span>(min!=dataRoot.getRight())&#123;</span><br><span class="line">						min.setRight(dataRoot.getRight());</span><br><span class="line">						setParent(dataRoot.getRight(),min);</span><br><span class="line">					&#125;</span><br><span class="line">					<span class="comment">//remove a black node,need fix color</span></span><br><span class="line">					<span class="keyword">if</span>(curMinIsBlack)&#123;</span><br><span class="line">						<span class="keyword">if</span>(min!=dataRoot.getRight())&#123;</span><br><span class="line">							fixRemove(x,isParent);</span><br><span class="line">						&#125;<span class="keyword">else</span> <span class="keyword">if</span>(min.getRight()!=<span class="literal">null</span>)&#123;</span><br><span class="line">							fixRemove(min.getRight(),<span class="literal">false</span>);</span><br><span class="line">						&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">							fixRemove(min,<span class="literal">true</span>);</span><br><span class="line">						&#125;</span><br><span class="line">					&#125;</span><br><span class="line">				&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">					setParent(dataRoot.getLeft(),parent);</span><br><span class="line">					<span class="keyword">if</span>(parent.getLeft()==dataRoot)&#123;</span><br><span class="line">						parent.setLeft(dataRoot.getLeft());</span><br><span class="line">					&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">						parent.setRight(dataRoot.getLeft());</span><br><span class="line">					&#125;</span><br><span class="line">					<span class="comment">//current node is black and tree is not empty</span></span><br><span class="line">					<span class="keyword">if</span>(dataRoot.isBlack() &amp;&amp; !(root.getLeft()==<span class="literal">null</span>))&#123;</span><br><span class="line">						RBTreeNode&lt;T&gt; x = dataRoot.getLeft()==<span class="literal">null</span> </span><br><span class="line">											? parent :dataRoot.getLeft();</span><br><span class="line">						<span class="type">boolean</span> <span class="variable">isParent</span> <span class="operator">=</span> dataRoot.getLeft()==<span class="literal">null</span>;</span><br><span class="line">						fixRemove(x,isParent);</span><br><span class="line">					&#125;</span><br><span class="line">				&#125;</span><br><span class="line">				setParent(dataRoot,<span class="literal">null</span>);</span><br><span class="line">				dataRoot.setLeft(<span class="literal">null</span>);</span><br><span class="line">				dataRoot.setRight(<span class="literal">null</span>);</span><br><span class="line">				<span class="keyword">if</span>(getRoot()!=<span class="literal">null</span>)&#123;</span><br><span class="line">					getRoot().setRed(<span class="literal">false</span>);</span><br><span class="line">					getRoot().setParent(<span class="literal">null</span>);</span><br><span class="line">				&#125;</span><br><span class="line">				size.decrementAndGet();</span><br><span class="line">				<span class="keyword">return</span> dataRoot.getValue();</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">/**</span></span><br><span class="line"><span class="comment">	 * fix remove action</span></span><br><span class="line"><span class="comment">	 * <span class="doctag">@param</span> node</span></span><br><span class="line"><span class="comment">	 * <span class="doctag">@param</span> isParent</span></span><br><span class="line"><span class="comment">	 */</span></span><br><span class="line">	<span class="keyword">private</span> <span class="keyword">void</span> <span class="title function_">fixRemove</span><span class="params">(RBTreeNode&lt;T&gt; node,<span class="type">boolean</span> isParent)</span>&#123;</span><br><span class="line">		RBTreeNode&lt;T&gt; cur = isParent ? <span class="literal">null</span> : node;</span><br><span class="line">		<span class="type">boolean</span> <span class="variable">isRed</span> <span class="operator">=</span> isParent ? <span class="literal">false</span> : node.isRed();</span><br><span class="line">		RBTreeNode&lt;T&gt; parent = isParent ? node : node.getParent();</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">while</span>(!isRed &amp;&amp; !isRoot(cur))&#123;</span><br><span class="line">			RBTreeNode&lt;T&gt; sibling = getSibling(cur,parent);</span><br><span class="line">			<span class="comment">//sibling is not null,due to before remove tree color is balance</span></span><br><span class="line">			</span><br><span class="line">			<span class="comment">//if cur is a left node</span></span><br><span class="line">			<span class="type">boolean</span> <span class="variable">isLeft</span> <span class="operator">=</span> parent.getRight()==sibling;</span><br><span class="line">			<span class="keyword">if</span>(sibling.isRed() &amp;&amp; !isLeft)&#123;<span class="comment">//示例1</span></span><br><span class="line">				<span class="comment">//cur in right</span></span><br><span class="line">				parent.makeRed();</span><br><span class="line">				sibling.makeBlack();</span><br><span class="line">				rotateRight(parent);</span><br><span class="line">			&#125;<span class="keyword">else</span> <span class="keyword">if</span>(sibling.isRed() &amp;&amp; isLeft)&#123;</span><br><span class="line">				<span class="comment">//cur in left</span></span><br><span class="line">				parent.makeRed();</span><br><span class="line">				sibling.makeBlack();</span><br><span class="line">				rotateLeft(parent);</span><br><span class="line">			&#125;<span class="keyword">else</span> <span class="keyword">if</span>(isBlack(sibling.getLeft()) &amp;&amp; isBlack(sibling.getRight()))&#123;<span class="comment">//示例2</span></span><br><span class="line">				sibling.makeRed();</span><br><span class="line">				cur = parent;</span><br><span class="line">				isRed = cur.isRed();</span><br><span class="line">				parent=parent.getParent();</span><br><span class="line">			&#125;<span class="keyword">else</span> <span class="keyword">if</span>(isLeft &amp;&amp; !isBlack(sibling.getLeft()) </span><br><span class="line">									&amp;&amp; isBlack(sibling.getRight()))&#123;<span class="comment">//示例3</span></span><br><span class="line">				sibling.makeRed();</span><br><span class="line">				sibling.getLeft().makeBlack();</span><br><span class="line">				rotateRight(sibling);</span><br><span class="line">			&#125;<span class="keyword">else</span> <span class="keyword">if</span>(!isLeft &amp;&amp; !isBlack(sibling.getRight()) </span><br><span class="line">											&amp;&amp; isBlack(sibling.getLeft()) )&#123;</span><br><span class="line">				sibling.makeRed();</span><br><span class="line">				sibling.getRight().makeBlack();</span><br><span class="line">				rotateLeft(sibling);</span><br><span class="line">			&#125;<span class="keyword">else</span> <span class="keyword">if</span>(isLeft &amp;&amp; !isBlack(sibling.getRight()))&#123;<span class="comment">//示例4</span></span><br><span class="line">				sibling.setRed(parent.isRed());</span><br><span class="line">				parent.makeBlack();</span><br><span class="line">				sibling.getRight().makeBlack();</span><br><span class="line">				rotateLeft(parent);</span><br><span class="line">				cur=getRoot();</span><br><span class="line">			&#125;<span class="keyword">else</span> <span class="keyword">if</span>(!isLeft &amp;&amp; !isBlack(sibling.getLeft()))&#123;</span><br><span class="line">				sibling.setRed(parent.isRed());</span><br><span class="line">				parent.makeBlack();</span><br><span class="line">				sibling.getLeft().makeBlack();</span><br><span class="line">				rotateRight(parent);</span><br><span class="line">				cur=getRoot();</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(isRed)&#123;</span><br><span class="line">			cur.makeBlack();</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(getRoot()!=<span class="literal">null</span>)&#123;</span><br><span class="line">			getRoot().setRed(<span class="literal">false</span>);</span><br><span class="line">			getRoot().setParent(<span class="literal">null</span>);</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">//get sibling node</span></span><br><span class="line">	<span class="keyword">private</span> RBTreeNode&lt;T&gt; <span class="title function_">getSibling</span><span class="params">(RBTreeNode&lt;T&gt; node,RBTreeNode&lt;T&gt; parent)</span>&#123;</span><br><span class="line">		parent = node==<span class="literal">null</span> ? parent : node.getParent();</span><br><span class="line">		<span class="keyword">if</span>(node==<span class="literal">null</span>)&#123;</span><br><span class="line">			<span class="keyword">return</span> parent.getLeft()==<span class="literal">null</span> ? parent.getRight() : parent.getLeft();</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(node==parent.getLeft())&#123;</span><br><span class="line">			<span class="keyword">return</span> parent.getRight();</span><br><span class="line">		&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">			<span class="keyword">return</span> parent.getLeft();</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">private</span> <span class="type">boolean</span> <span class="title function_">isBlack</span><span class="params">(RBTreeNode&lt;T&gt; node)</span>&#123;</span><br><span class="line">		<span class="keyword">return</span> node==<span class="literal">null</span> || node.isBlack();</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">private</span> <span class="type">boolean</span> <span class="title function_">isRoot</span><span class="params">(RBTreeNode&lt;T&gt; node)</span>&#123;</span><br><span class="line">		<span class="keyword">return</span> root.getLeft() == node &amp;&amp; node.getParent()==<span class="literal">null</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">/**</span></span><br><span class="line"><span class="comment">	 * find the successor node</span></span><br><span class="line"><span class="comment">	 * <span class="doctag">@param</span> node current node&#x27;s right node</span></span><br><span class="line"><span class="comment">	 * <span class="doctag">@return</span></span></span><br><span class="line"><span class="comment">	 */</span></span><br><span class="line">	<span class="keyword">private</span> RBTreeNode&lt;T&gt; <span class="title function_">removeMin</span><span class="params">(RBTreeNode&lt;T&gt; node)</span>&#123;</span><br><span class="line">		<span class="comment">//find the min node</span></span><br><span class="line">		RBTreeNode&lt;T&gt; parent = node;</span><br><span class="line">		<span class="keyword">while</span>(node!=<span class="literal">null</span> &amp;&amp; node.getLeft()!=<span class="literal">null</span>)&#123;</span><br><span class="line">			parent = node;</span><br><span class="line">			node = node.getLeft();</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="comment">//remove min node</span></span><br><span class="line">		<span class="keyword">if</span>(parent==node)&#123;</span><br><span class="line">			<span class="keyword">return</span> node;</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		parent.setLeft(node.getRight());</span><br><span class="line">		setParent(node.getRight(),parent);</span><br><span class="line">		</span><br><span class="line">		<span class="comment">//don&#x27;t remove right pointer,it is used for fixed color balance</span></span><br><span class="line">		<span class="comment">//node.setRight(null);</span></span><br><span class="line">		<span class="keyword">return</span> node;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">private</span> T <span class="title function_">addNode</span><span class="params">(RBTreeNode&lt;T&gt; node)</span>&#123;</span><br><span class="line">		node.setLeft(<span class="literal">null</span>);</span><br><span class="line">		node.setRight(<span class="literal">null</span>);</span><br><span class="line">		node.setRed(<span class="literal">true</span>);</span><br><span class="line">		setParent(node,<span class="literal">null</span>);</span><br><span class="line">		<span class="keyword">if</span>(root.getLeft()==<span class="literal">null</span>)&#123;</span><br><span class="line">			root.setLeft(node);</span><br><span class="line">			<span class="comment">//root node is black</span></span><br><span class="line">			node.setRed(<span class="literal">false</span>);</span><br><span class="line">			size.incrementAndGet();</span><br><span class="line">		&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">			RBTreeNode&lt;T&gt; x = findParentNode(node);</span><br><span class="line">			<span class="type">int</span> <span class="variable">cmp</span> <span class="operator">=</span> x.getValue().compareTo(node.getValue());</span><br><span class="line">			</span><br><span class="line">			<span class="keyword">if</span>(<span class="built_in">this</span>.overrideMode &amp;&amp; cmp==<span class="number">0</span>)&#123;</span><br><span class="line">				<span class="type">T</span> <span class="variable">v</span> <span class="operator">=</span> x.getValue();</span><br><span class="line">				x.setValue(node.getValue());</span><br><span class="line">				<span class="keyword">return</span> v;</span><br><span class="line">			&#125;<span class="keyword">else</span> <span class="keyword">if</span>(cmp==<span class="number">0</span>)&#123;</span><br><span class="line">				<span class="comment">//value exists,ignore this node</span></span><br><span class="line">				<span class="keyword">return</span> x.getValue();</span><br><span class="line">			&#125;</span><br><span class="line">			</span><br><span class="line">			setParent(node,x);</span><br><span class="line">			</span><br><span class="line">			<span class="keyword">if</span>(cmp&gt;<span class="number">0</span>)&#123;</span><br><span class="line">				x.setLeft(node);</span><br><span class="line">			&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">				x.setRight(node);</span><br><span class="line">			&#125;</span><br><span class="line">			</span><br><span class="line">			fixInsert(node);</span><br><span class="line">			size.incrementAndGet();</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="comment">/**</span></span><br><span class="line"><span class="comment">	 * find the parent node to hold node x,if parent value equals x.value return parent.</span></span><br><span class="line"><span class="comment">	 * <span class="doctag">@param</span> x</span></span><br><span class="line"><span class="comment">	 * <span class="doctag">@return</span></span></span><br><span class="line"><span class="comment">	 */</span></span><br><span class="line">	<span class="keyword">private</span> RBTreeNode&lt;T&gt; <span class="title function_">findParentNode</span><span class="params">(RBTreeNode&lt;T&gt; x)</span>&#123;</span><br><span class="line">		RBTreeNode&lt;T&gt; dataRoot = getRoot();</span><br><span class="line">		RBTreeNode&lt;T&gt; child = dataRoot;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">while</span>(child!=<span class="literal">null</span>)&#123;</span><br><span class="line">			<span class="type">int</span> <span class="variable">cmp</span> <span class="operator">=</span> child.getValue().compareTo(x.getValue());</span><br><span class="line">			<span class="keyword">if</span>(cmp==<span class="number">0</span>)&#123;</span><br><span class="line">				<span class="keyword">return</span> child;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">if</span>(cmp&gt;<span class="number">0</span>)&#123;</span><br><span class="line">				dataRoot = child;</span><br><span class="line">				child = child.getLeft();</span><br><span class="line">			&#125;<span class="keyword">else</span> <span class="keyword">if</span>(cmp&lt;<span class="number">0</span>)&#123;</span><br><span class="line">				dataRoot = child;</span><br><span class="line">				child = child.getRight();</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> dataRoot;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="comment">/**</span></span><br><span class="line"><span class="comment">	 * red black tree insert fix.</span></span><br><span class="line"><span class="comment">	 * <span class="doctag">@param</span> x</span></span><br><span class="line"><span class="comment">	 */</span></span><br><span class="line">	<span class="keyword">private</span> <span class="keyword">void</span> <span class="title function_">fixInsert</span><span class="params">(RBTreeNode&lt;T&gt; x)</span>&#123;</span><br><span class="line">		RBTreeNode&lt;T&gt; parent = x.getParent();</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">while</span>(parent!=<span class="literal">null</span> &amp;&amp; parent.isRed())&#123;</span><br><span class="line">			RBTreeNode&lt;T&gt; uncle = getUncle(x);</span><br><span class="line">			<span class="keyword">if</span>(uncle==<span class="literal">null</span>)&#123;<span class="comment">//need to rotate</span></span><br><span class="line">				RBTreeNode&lt;T&gt; ancestor = parent.getParent();</span><br><span class="line">				<span class="comment">//ancestor is not null due to before before add,tree color is balance</span></span><br><span class="line">				<span class="keyword">if</span>(parent == ancestor.getLeft())&#123;</span><br><span class="line">					<span class="type">boolean</span> <span class="variable">isRight</span> <span class="operator">=</span> x == parent.getRight();</span><br><span class="line">					<span class="keyword">if</span>(isRight)&#123;</span><br><span class="line">						rotateLeft(parent);</span><br><span class="line">					&#125;</span><br><span class="line">					rotateRight(ancestor);</span><br><span class="line">					</span><br><span class="line">					<span class="keyword">if</span>(isRight)&#123;</span><br><span class="line">						x.setRed(<span class="literal">false</span>);</span><br><span class="line">						parent=<span class="literal">null</span>;<span class="comment">//end loop</span></span><br><span class="line">					&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">						parent.setRed(<span class="literal">false</span>);</span><br><span class="line">					&#125;</span><br><span class="line">					ancestor.setRed(<span class="literal">true</span>);</span><br><span class="line">				&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">					<span class="type">boolean</span> <span class="variable">isLeft</span> <span class="operator">=</span> x == parent.getLeft();</span><br><span class="line">					<span class="keyword">if</span>(isLeft)&#123;</span><br><span class="line">						rotateRight(parent);</span><br><span class="line">					&#125;</span><br><span class="line">					rotateLeft(ancestor);</span><br><span class="line">					</span><br><span class="line">					<span class="keyword">if</span>(isLeft)&#123;</span><br><span class="line">						x.setRed(<span class="literal">false</span>);</span><br><span class="line">						parent=<span class="literal">null</span>;<span class="comment">//end loop</span></span><br><span class="line">					&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">						parent.setRed(<span class="literal">false</span>);</span><br><span class="line">					&#125;</span><br><span class="line">					ancestor.setRed(<span class="literal">true</span>);</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;<span class="keyword">else</span>&#123;<span class="comment">//uncle is red</span></span><br><span class="line">				parent.setRed(<span class="literal">false</span>);</span><br><span class="line">				uncle.setRed(<span class="literal">false</span>);</span><br><span class="line">				parent.getParent().setRed(<span class="literal">true</span>);</span><br><span class="line">				x=parent.getParent();</span><br><span class="line">				parent = x.getParent();</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		getRoot().makeBlack();</span><br><span class="line">		getRoot().setParent(<span class="literal">null</span>);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">/**</span></span><br><span class="line"><span class="comment">	 * get uncle node</span></span><br><span class="line"><span class="comment">	 * <span class="doctag">@param</span> node</span></span><br><span class="line"><span class="comment">	 * <span class="doctag">@return</span></span></span><br><span class="line"><span class="comment">	 */</span></span><br><span class="line">	<span class="keyword">private</span> RBTreeNode&lt;T&gt; <span class="title function_">getUncle</span><span class="params">(RBTreeNode&lt;T&gt; node)</span>&#123;</span><br><span class="line">		RBTreeNode&lt;T&gt; parent = node.getParent();</span><br><span class="line">		RBTreeNode&lt;T&gt; ancestor = parent.getParent();</span><br><span class="line">		<span class="keyword">if</span>(ancestor==<span class="literal">null</span>)&#123;</span><br><span class="line">			<span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(parent == ancestor.getLeft())&#123;</span><br><span class="line">			<span class="keyword">return</span> ancestor.getRight();</span><br><span class="line">		&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">			<span class="keyword">return</span> ancestor.getLeft();</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">private</span> <span class="keyword">void</span> <span class="title function_">rotateLeft</span><span class="params">(RBTreeNode&lt;T&gt; node)</span>&#123;</span><br><span class="line">		RBTreeNode&lt;T&gt; right = node.getRight();</span><br><span class="line">		<span class="keyword">if</span>(right==<span class="literal">null</span>)&#123;</span><br><span class="line">			<span class="keyword">throw</span> <span class="keyword">new</span> <span class="title class_">java</span>.lang.IllegalStateException(<span class="string">&quot;right node is null&quot;</span>);</span><br><span class="line">		&#125;</span><br><span class="line">		RBTreeNode&lt;T&gt; parent = node.getParent();</span><br><span class="line">		node.setRight(right.getLeft());</span><br><span class="line">		setParent(right.getLeft(),node);</span><br><span class="line">		</span><br><span class="line">		right.setLeft(node);</span><br><span class="line">		setParent(node,right);</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">if</span>(parent==<span class="literal">null</span>)&#123;<span class="comment">//node pointer to root</span></span><br><span class="line">			<span class="comment">//right  raise to root node</span></span><br><span class="line">			root.setLeft(right);</span><br><span class="line">			setParent(right,<span class="literal">null</span>);</span><br><span class="line">		&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">			<span class="keyword">if</span>(parent.getLeft()==node)&#123;</span><br><span class="line">				parent.setLeft(right);</span><br><span class="line">			&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">				parent.setRight(right);</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="comment">//right.setParent(parent);</span></span><br><span class="line">			setParent(right,parent);</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">private</span> <span class="keyword">void</span> <span class="title function_">rotateRight</span><span class="params">(RBTreeNode&lt;T&gt; node)</span>&#123;</span><br><span class="line">		RBTreeNode&lt;T&gt; left = node.getLeft();</span><br><span class="line">		<span class="keyword">if</span>(left==<span class="literal">null</span>)&#123;</span><br><span class="line">			<span class="keyword">throw</span> <span class="keyword">new</span> <span class="title class_">java</span>.lang.IllegalStateException(<span class="string">&quot;left node is null&quot;</span>);</span><br><span class="line">		&#125;</span><br><span class="line">		RBTreeNode&lt;T&gt; parent = node.getParent();</span><br><span class="line">		node.setLeft(left.getRight());</span><br><span class="line">		setParent(left.getRight(),node);</span><br><span class="line">		</span><br><span class="line">		left.setRight(node);</span><br><span class="line">		setParent(node,left);</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">if</span>(parent==<span class="literal">null</span>)&#123;</span><br><span class="line">			root.setLeft(left);</span><br><span class="line">			setParent(left,<span class="literal">null</span>);</span><br><span class="line">		&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">			<span class="keyword">if</span>(parent.getLeft()==node)&#123;</span><br><span class="line">				parent.setLeft(left);</span><br><span class="line">			&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">				parent.setRight(left);</span><br><span class="line">			&#125;</span><br><span class="line">			setParent(left,parent);</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">private</span> <span class="keyword">void</span> <span class="title function_">setParent</span><span class="params">(RBTreeNode&lt;T&gt; node,RBTreeNode&lt;T&gt; parent)</span>&#123;</span><br><span class="line">		<span class="keyword">if</span>(node!=<span class="literal">null</span>)&#123;</span><br><span class="line">			node.setParent(parent);</span><br><span class="line">			<span class="keyword">if</span>(parent==root)&#123;</span><br><span class="line">				node.setParent(<span class="literal">null</span>);</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">/**</span></span><br><span class="line"><span class="comment">	 * debug method,it used print the given node and its children nodes,</span></span><br><span class="line"><span class="comment">	 * every layer output in one line</span></span><br><span class="line"><span class="comment">	 * <span class="doctag">@param</span> root</span></span><br><span class="line"><span class="comment">	 */</span></span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">printTree</span><span class="params">(RBTreeNode&lt;T&gt; root)</span>&#123;</span><br><span class="line">		java.util.LinkedList&lt;RBTreeNode&lt;T&gt;&gt; queue =<span class="keyword">new</span> <span class="title class_">java</span>.util.LinkedList&lt;RBTreeNode&lt;T&gt;&gt;();</span><br><span class="line">		java.util.LinkedList&lt;RBTreeNode&lt;T&gt;&gt; queue2 =<span class="keyword">new</span> <span class="title class_">java</span>.util.LinkedList&lt;RBTreeNode&lt;T&gt;&gt;();</span><br><span class="line">		<span class="keyword">if</span>(root==<span class="literal">null</span>)&#123;</span><br><span class="line">			<span class="keyword">return</span> ;</span><br><span class="line">		&#125;</span><br><span class="line">		queue.add(root);</span><br><span class="line">		<span class="type">boolean</span> <span class="variable">firstQueue</span> <span class="operator">=</span> <span class="literal">true</span>;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">while</span>(!queue.isEmpty() || !queue2.isEmpty())&#123;</span><br><span class="line">			java.util.LinkedList&lt;RBTreeNode&lt;T&gt;&gt; q = firstQueue ? queue : queue2;</span><br><span class="line">			RBTreeNode&lt;T&gt; n = q.poll();</span><br><span class="line">			</span><br><span class="line">			<span class="keyword">if</span>(n!=<span class="literal">null</span>)&#123;</span><br><span class="line">				<span class="type">String</span> <span class="variable">pos</span> <span class="operator">=</span> n.getParent()==<span class="literal">null</span> ? <span class="string">&quot;&quot;</span> : ( n == n.getParent().getLeft() ? <span class="string">&quot; LE&quot;</span> : <span class="string">&quot; RI&quot;</span>);</span><br><span class="line">				<span class="type">String</span> <span class="variable">pstr</span> <span class="operator">=</span> n.getParent()==<span class="literal">null</span> ? <span class="string">&quot;&quot;</span> : n.getParent().toString();</span><br><span class="line">				<span class="type">String</span> <span class="variable">cstr</span> <span class="operator">=</span> n.isRed()?<span class="string">&quot;R&quot;</span>:<span class="string">&quot;B&quot;</span>;</span><br><span class="line">				cstr = n.getParent()==<span class="literal">null</span> ? cstr : cstr+<span class="string">&quot; &quot;</span>;</span><br><span class="line">				System.out.print(n+<span class="string">&quot;(&quot;</span>+(cstr)+pstr+(pos)+<span class="string">&quot;)&quot;</span>+<span class="string">&quot;\t&quot;</span>);</span><br><span class="line">				<span class="keyword">if</span>(n.getLeft()!=<span class="literal">null</span>)&#123;</span><br><span class="line">					(firstQueue ? queue2 : queue).add(n.getLeft());</span><br><span class="line">				&#125;</span><br><span class="line">				<span class="keyword">if</span>(n.getRight()!=<span class="literal">null</span>)&#123;</span><br><span class="line">					(firstQueue ? queue2 : queue).add(n.getRight());</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">				System.out.println();</span><br><span class="line">				firstQueue = !firstQueue;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line">		RBTree&lt;String&gt; bst = <span class="keyword">new</span> <span class="title class_">RBTree</span>&lt;String&gt;();</span><br><span class="line">		bst.addNode(<span class="string">&quot;d&quot;</span>);</span><br><span class="line">		bst.addNode(<span class="string">&quot;d&quot;</span>);</span><br><span class="line">		bst.addNode(<span class="string">&quot;c&quot;</span>);</span><br><span class="line">		bst.addNode(<span class="string">&quot;c&quot;</span>);</span><br><span class="line">		bst.addNode(<span class="string">&quot;b&quot;</span>);</span><br><span class="line">		bst.addNode(<span class="string">&quot;f&quot;</span>);</span><br><span class="line">		</span><br><span class="line">		bst.addNode(<span class="string">&quot;a&quot;</span>);</span><br><span class="line">		bst.addNode(<span class="string">&quot;e&quot;</span>);</span><br><span class="line">		</span><br><span class="line">		bst.addNode(<span class="string">&quot;g&quot;</span>);</span><br><span class="line">		bst.addNode(<span class="string">&quot;h&quot;</span>);</span><br><span class="line"></span><br><span class="line">		</span><br><span class="line">		bst.remove(<span class="string">&quot;c&quot;</span>);</span><br><span class="line"></span><br><span class="line">		bst.printTree(bst.getRoot());</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>代码调试的时候，printTree输出格式如下: </p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line">d(B)</span><br><span class="line">b(B d LE) g(R d RI)</span><br><span class="line">a(R b LE) e(B g LE) h(B g RI)</span><br><span class="line">f(R e RI)</span><br></pre></td></tr></table></figure>

<p>括号左边表示元素的内容。括号内的第一个元素表示颜色，B表示black，R表示red；第二个元素表示父元素的值；第三个元素表示左右，LE表示在父元素的左边。RI表示在父元素的右边。</p>
<p>第一个元素d是root节点，由于它没有父节点，所以括号内只有一个元素。</p>
<h2 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h2><p>作为平衡二叉查找树里面众多的实现之一，红黑树无疑是最简洁、实现最为简单的。红黑树通过引入颜色的概念，通过颜色这个约束条件的使用来保持树的高度平衡。作为平衡二叉查找树，旋转是一个必不可少的操作。通过旋转可以降低树的高度，在红黑树里面还可以转换颜色。</p>
<p>红黑树里面的插入和删除的操作比较难理解，这时要注意记住一点：操作之前红黑树是平衡的，颜色是符合定义的。在操作的时候就需要向兄弟节点、父节点、侄子节点借调和互换颜色，要达到这个目的，就需要不断的进行旋转。所以红黑树的插入删除操作需要不停的旋转，一旦借调了别的节点，删除和插入的节点就会达到局部的平衡（局部符合红黑树的定义），但是被借调的节点就不会平衡了，这时就需要以被借调的节点为起点继续进行调整，直到整棵树都是平衡的。在整个修复的过程中，插入具体的分为3种情况，删除分为4种情况。</p>
<p>整个红黑树的查找，插入和删除都是O(logN)的，原因就是整个红黑树的高度是logN，查找从根到叶，走过的路径是树的高度，删除和插入操作是从叶到根的，所以经过的路径都是logN。</p>
<h2 id="参考文献"><a href="#参考文献" class="headerlink" title="参考文献"></a>参考文献</h2><ul>
<li>Cormen T H, Leiserson C E, Rivest R L, 等. 算法导论（第3版）. 殷建平, 等. 机械工业出版社, 2012.</li>
<li>Sedgewick R, Wayne K. 算法（第4版）. 谢路云 译. 人民邮电出版社, 2012.</li>
<li>Weiss M A. 数据结构与算法分析（第2版）. 冯舜玺 译. 机械工业出版社, 2004.</li>
<li>Knuth D E. 计算机程序设计艺术 卷3：排序与查找（英文版 第2版）. 人民邮电出版社, 2010.</li>
<li><a target="_blank" rel="noopener" href="https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91/10905079?fromtitle=%E4%BA%8C%E5%8F%89%E6%9F%A5%E6%89%BE%E6%A0%91&fromid=7077965">二叉查找树百度百科</a></li>
<li><a target="_blank" rel="noopener" href="https://baike.baidu.com/item/%E7%BA%A2%E9%BB%91%E6%A0%91">RB红黑树百度百科</a></li>
</ul>
</section>
    <!-- Tags START -->
    
      <div class="tags">
        <span>Tags:</span>
        
  <a href="/tags#二叉树" >
    <span class="tag-code">二叉树</span>
  </a>

      </div>
    
    <!-- Tags END -->
    <!-- NAV START -->
    
  <div class="nav-container">
    <!-- reverse left and right to put prev and next in a more logic postition -->
    
      <a class="nav-left" href="/2019/03/28/%E8%B0%88%E8%B0%88%E5%9B%BD%E5%86%85%E5%A4%A7%E7%8E%AF%E5%A2%83%E4%B8%8B%E7%9A%84996%E5%8A%A0%E7%8F%AD%E6%96%87%E5%8C%96/">
        <span class="nav-arrow">← </span>
        
          谈谈国内大环境下的996加班文化
        
      </a>
    
    
      <a class="nav-right" href="/2019/04/02/%E8%81%8A%E8%81%8AJava%E9%94%81%E7%9A%84%E9%82%A3%E4%BA%9B%E4%BA%8B/">
        
          聊聊Java锁的那些事
        
        <span class="nav-arrow"> →</span>
      </a>
    
  </div>

    <!-- NAV END -->
    <!-- 打赏 START -->
    
      <div class="money-like">
        <div class="reward-btn">
          赏
          <span class="money-code">
            <span class="alipay-code">
              <div class="code-image"></div>
              <b>使用支付宝打赏</b>
            </span>
            <span class="wechat-code">
              <div class="code-image"></div>
              <b>使用微信打赏</b>
            </span>
          </span>
        </div>
        <p class="notice">若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏</p>
      </div>
    
    <!-- 打赏 END -->
    <!-- 二维码 START -->
    
      <div class="qrcode">
        <canvas id="share-qrcode"></canvas>
        <p class="notice">扫描二维码，分享此文章</p>
      </div>
    
    <!-- 二维码 END -->
    
      <!-- Utterances START -->
      <div id="utterances"></div>
      <script src="https://utteranc.es/client.js"
        repo="ltyeamin/blogtalks"
        issue-term="pathname"
        theme="github-light"
        crossorigin="anonymous"
        async></script>    
      <!-- Utterances END -->
    
  </article>
  <!-- Article END -->
  <!-- Catalog START -->
  
    <aside class="catalog-container">
  <div class="toc-main">
    <strong class="toc-title">Catalog</strong>
    
      <ol class="toc-nav"><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#%E4%BA%8C%E5%8F%89%E6%9F%A5%E6%89%BE%E6%A0%91"><span class="toc-nav-text">二叉查找树</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#%E5%9F%BA%E6%9C%AC%E6%A6%82%E5%BF%B5"><span class="toc-nav-text">基本概念</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#%E5%9F%BA%E6%9C%AC%E6%93%8D%E4%BD%9C"><span class="toc-nav-text">基本操作</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-4"><a class="toc-nav-link" href="#%E6%9F%A5%E6%89%BE"><span class="toc-nav-text">查找</span></a></li><li class="toc-nav-item toc-nav-level-4"><a class="toc-nav-link" href="#%E6%8F%92%E5%85%A5"><span class="toc-nav-text">插入</span></a></li><li class="toc-nav-item toc-nav-level-4"><a class="toc-nav-link" href="#%E5%88%A0%E9%99%A4"><span class="toc-nav-text">删除</span></a></li></ol></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#%E5%AD%98%E5%9C%A8%E7%9A%84%E5%BC%8A%E7%AB%AF"><span class="toc-nav-text">存在的弊端</span></a></li></ol></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#RB%E7%BA%A2%E9%BB%91%E6%A0%91"><span class="toc-nav-text">RB红黑树</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#%E5%9F%BA%E6%9C%AC%E6%A6%82%E5%BF%B5-1"><span class="toc-nav-text">基本概念</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#%E5%9F%BA%E6%9C%AC%E5%AE%9A%E4%B9%89"><span class="toc-nav-text">基本定义</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#%E5%9F%BA%E6%9C%AC%E6%93%8D%E4%BD%9C-1"><span class="toc-nav-text">基本操作</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-4"><a class="toc-nav-link" href="#%E6%97%8B%E8%BD%AC%E6%93%8D%E4%BD%9C"><span class="toc-nav-text">旋转操作</span></a></li><li class="toc-nav-item toc-nav-level-4"><a class="toc-nav-link" href="#%E6%9F%A5%E6%89%BE%E6%93%8D%E4%BD%9C"><span class="toc-nav-text">查找操作</span></a></li><li class="toc-nav-item toc-nav-level-4"><a class="toc-nav-link" href="#%E6%8F%92%E5%85%A5%E6%93%8D%E4%BD%9C"><span class="toc-nav-text">插入操作</span></a></li><li class="toc-nav-item toc-nav-level-4"><a class="toc-nav-link" href="#%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C"><span class="toc-nav-text">删除操作</span></a></li></ol></li></ol></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#RB%E7%BA%A2%E9%BB%91%E6%A0%91%E7%9A%84Java%E5%AE%9E%E7%8E%B0"><span class="toc-nav-text">RB红黑树的Java实现</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#%E6%80%BB%E7%BB%93"><span class="toc-nav-text">总结</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#%E5%8F%82%E8%80%83%E6%96%87%E7%8C%AE"><span class="toc-nav-text">参考文献</span></a></li></ol>
    
  </div>
</aside>
  
  <!-- Catalog END -->
</main>

<script>
  (function () {
    var url = 'http://example.com/2019/03/29/红黑树深入剖析及Java实现/';
    var banner = ''
    if (banner !== '' && banner !== 'undefined' && banner !== 'null') {
      $('#article-banner').css({
        'background-image': 'url(' + banner + ')'
      })
    } else {
      $('#article-banner').geopattern(url)
    }
    $('.header').removeClass('fixed-header')

    // error image
    $(".markdown-content img").on('error', function() {
      $(this).attr('src', '/css/images/error_icon.png')
      $(this).css({
        'cursor': 'default'
      })
    })

    // zoom image
    $(".markdown-content img").on('click', function() {
      var src = $(this).attr('src')
      if (src !== '/css/images/error_icon.png') {
        var imageW = $(this).width()
        var imageH = $(this).height()

        var zoom = ($(window).width() * 0.95 / imageW).toFixed(2)
        zoom = zoom < 1 ? 1 : zoom
        zoom = zoom > 2 ? 2 : zoom
        var transY = (($(window).height() - imageH) / 2).toFixed(2)

        $('body').append('<div class="image-view-wrap"><div class="image-view-inner"><img src="'+ src +'" /></div></div>')
        $('.image-view-wrap').addClass('wrap-active')
        $('.image-view-wrap img').css({
          'width': `${imageW}`,
          'transform': `translate3d(0, ${transY}px, 0) scale3d(${zoom}, ${zoom}, 1)`
        })
        $('html').css('overflow', 'hidden')

        $('.image-view-wrap').on('click', function() {
          $(this).remove()
          $('html').attr('style', '')
        })
      }
    })
  })();
</script>


  <script>
    var qr = new QRious({
      element: document.getElementById('share-qrcode'),
      value: document.location.href
    });
  </script>






    <div class="scroll-top">
  <span class="arrow-icon"></span>
</div>
    <footer class="app-footer">
  <p class="copyright">
    &copy; 2024 | Proudly powered by <a href="https://hexo.io" target="_blank">Hexo</a>
    <br>
    Theme by <a target="_blank" rel="noopener" href="https://github.com/ltyeamin">tong.li</a>
  </p>
</footer>

<script>
  function async(u, c) {
    var d = document, t = 'script',
      o = d.createElement(t),
      s = d.getElementsByTagName(t)[0];
    o.src = u;
    if (c) { o.addEventListener('load', function (e) { c(null, e); }, false); }
    s.parentNode.insertBefore(o, s);
  }
</script>
<script>
  async("https://cdn.staticfile.org/fastclick/1.0.6/fastclick.min.js", function(){
    FastClick.attach(document.body);
  })
</script>

<script>
  var hasLine = 'true';
  async("https://cdn.staticfile.org/highlight.js/9.12.0/highlight.min.js", function(){
    $('figure pre').each(function(i, block) {
      var figure = $(this).parents('figure');
      if (hasLine === 'false') {
        figure.find('.gutter').hide();
      }
      hljs.configure({useBR: true});
      var lang = figure.attr('class').split(' ')[1] || 'code';
      var codeHtml = $(this).html();
      var codeTag = document.createElement('code');
      codeTag.className = lang;
      codeTag.innerHTML = codeHtml;
      $(this).attr('class', '').empty().html(codeTag);
      figure.attr('data-lang', lang.toUpperCase());
      hljs.highlightBlock(block);
    });
  })
</script>
<!-- Baidu Tongji -->



<script src='https://cdn.staticfile.org/mermaid/8.11.2/mermaid.min.js'></script>



<script src="/js/script.js"></script>


  </body>
</html>